Longest valid parentheses

Time: O(N); Space: O(1); hard

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = “(()”

Output: 2

Explanation:

  • The longest valid parentheses substring is “()”

Example 2:

Input: s = “)()())”

Output: 4

Explanation:

  • Where the longest valid parentheses substring is “()()”

[1]:

class Solution1(object):
    def longestValidParentheses(self, s) -> int:
        """
        :type s: str
        :rtype: int
        """
        def length(it, start, c):
            depth, longest = 0, 0
            for i in it:
                if s[i] == c:
                    depth += 1
                else:
                    depth -= 1
                    if depth < 0:
                        start, depth = i, 0
                    elif depth == 0:
                        longest = max(longest, abs(i - start))
            return longest

        return max(length(range(len(s)), -1, '('), \
                   length(reversed(range(len(s))), len(s), ')'))

[2]:

sol = Solution1()
s = "(()"
assert sol.longestValidParentheses(s) == 2
s = ")()())"
assert sol.longestValidParentheses(s) == 4

[3]:

class Solution2(object):
    def longestValidParentheses(self, s) -> int:
        '''
        :type  s: str
        :rtype: int
        Time: O(N); Space: O(N)
        '''
        longest, last, indices = 0, -1, []
        for i in range(len(s)):
            if s[i] == '(':
                indices.append(i)
            elif not indices:
                last = i
            else:
                indices.pop()
                if not indices:
                    longest = max(longest, i - last)
                else:
                    longest = max(longest, i - indices[-1])
        return longest

[4]:

sol = Solution2()
s = "(()"
assert sol.longestValidParentheses(s) == 2
s = ")()())"
assert sol.longestValidParentheses(s) == 4